1. FIELD OF THE INVENTION
This invention relates to vector processing system and, particularly, to a vector processing system suitable for vector process used frequently in data base processing in which the type of operation is changed during a process.
2. DESCRIPTION OF THE PRIOR ART
In a vector processing system, with vector data being sorted in two groups, the bitonic method for sorting the whole vector data has conventionally been implemented on a software basis. The bitonic method is as follows. For example, when it is intended to sort elements of data in the ascending order of data elements with the assumption that the left half of the data is aligned so that its contiguous data elements have an equal value or values in the increasing (i.e., ascending) order and the right half of the data is aligned so that its contiguous data elements have an equal value or values in the decreasing (i.e., descending) order, an element of the right-hand data is compared with the counterpart of the left-hand data, e.g., comparison between the first element in the right-hand data and that in the left-hand data, and if the element value of the right-hand data is equal to or larger than the element value of the left-hand data, the element position is left unchanged, or if the comparison result is opposite, the element positions are exchanged and the above operation is implemented for all data elements. Subsequently, each of the right-hand and left-hand data is further divided into two parts and the above operation is carried out. These operations are repeated until the operation for two adjoining elements completes. For sorting data elements in the descending order, positions of elements are changed reversely in the above operation. According to the bitonic sorting method, each element in the left hand part of data is made equal to or larger than any element in the right half part in the case of the above example, and sorting is carried out by continuing the operation up to the operation for two elements. Generally, in sorting vector data, it is divided into 2-element groups and sorting is carried out in the ascending order for even-numbered groups (counted from one end) and in the descending order for odd-numbered groups. Subsequently, sorting is carried out for 4-element groups, in the ascending order for odd-numbered groups and in the descending order for even-numbered groups. In this way, the final sorting result is reached, and the sorting operation in each stage can be implemented by the bitonic method.
Sorting in the bitonic method on a hardware basis poses the following problems. Vector data to be sorted by the bitonic method includes, at random, parts which output elements that are not larger in value than an input vector element to be compared and parts which output elements that are not smaller in value than the input vector element. Conventional vector processing processors cannot cope with these cases by one type of instruction. For example, in processor HITAC S-810, as described in its manual on pages 83, 117 and 119, it is necessary for the sorting to use two instructions including the instruction for testing whether one element is equal to, larger than, or smaller than another element and the instruction for testing whether one element is equal to, smaller than, or larger than another element, and in this case vector data to be sorted must be divided into a part outputting elements that are not larger than an input element and a part outputting elements that are not smaller than the input element, and the instructions must be executed separately for these parts. Execution of a vector instruction necessitates initial setting and readout of operation result, and execution of two types of instruction results in doubled overhead. In addition, the performance of sorting falls as the vector length decreases. As it is described in publication entitled "Sorting and Searching", Vol. 3, Chapter 5, pp. 232-233, by Knuth, as the algorithm of the bitonic sorting method advances the length of a divided vector becomes shorter and the performance falls significantly.
In the bitonic sorting method of the case where vector data is divided and bitonic sorting is implemented for each division and of the case where sorting of one division is followed by sorting of the next division, the increment of the reading and writing address for each element of vector must be changed when the division to be operated changes. In conventional vector processing systems, the address increment is constant during the execution of one vector instruction, and therefore the need of executing a different vector instruction at each change of the address increment value causes an increased overhead such as for initial setting.